#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>

using namespace std;

class Solution {
public:
    int maximumDifference(vector<int>& nums) {
        int ret = -1;

        stack<int> stk;
        int bottom;
        for (const auto& num : nums) {
            while (!stk.empty() && num < stk.top()) {
                stk.pop();
            }

            if (stk.empty()) {
                bottom = num;
            }

            stk.push(num);

            ret = max(ret, (stk.top() == bottom)? -1 : stk.top() - bottom);
        }
        return ret;
    }
};


int main()
{
    Solution s;
    vector<int> vt{87,68,91,86,58,63,43,98,6,40};
    int ret = s.maximumDifference(vt);
    cout << ret << endl;

    return 0;
}